{\magonebf  6.3 Sets of two-dimensional points (point\_set)}

An instance $S$ of the data type $point\_set$ is a collection of items 
($ps\_item$). Every item in $S$ contains a two-dimensional point as key
(data type $point$), and an information from a data type $I$, called 
the information type of $S$. The number of items in $S$ is called the size of 
$S$. A point set of size zero is said to be empty. We use $<p,i>$ to denote the 
item with point $p$, and information $i$. For each  point $p$ there is at most 
one item $<p,i> \in S$. Beside the normal dictionary operations, the data
type $point\_set$ provides operations for rectangular range queries and
nearest neighbor queries. 


\bigskip
{\bf 1. Declaration of a two-dimensional point set type}

\decl point\_set I

introduces a new data type with name \name\ consisting of all 
two-dimensional point sets  with information type $I$. 


\bigskip
{\bf 2. Creation of a two-dimensional point set}


\create S {}

creates an instance \var\ of type \name\ and initializes \var\ to the 
empty set. 



\bigskip
{\bf 3. \operations}

\+\cleartabs & \hskip 2.6truecm & \hskip 6truecm &\cr
\+\op point          key {ps\_item\ it}   
                      {returns the point of item $it$.}
\+\nop                {\precond $it$ is an item in \var.}
\smallskip
\+\op I              inf {ps\_item\ it}   
                      {returns the information of item $it$.}
\+\nop                {\precond $it$ is an item in \var.}
\smallskip
\+\op ps\_item       insert {point\ p,\ I\ i} 
                      {associates the information $i$ with point $p$.}
\+\nop                {If there is an item $<p,j>$ in \var\ then $j$}
\+\nop                {is replaced by $i$, else a new item $<p,i>$}
\+\nop                {is added to $S$. In both cases the item is}
\+\nop                {returned.}
\smallskip
\+\op ps\_item       lookup {point\ p} 
                      {returns the item with point $p$ (nil if no}
\+\nop                {such item exists in \var).}
\smallskip
\+\op ps\_item       nearest\_neighbor {point\ q}
                      {returns the item $<p,i>\ \in\ S$ such that}
\+\nop                {the distance between $p$ and $q$ is minimal.}
\smallskip
\+\op list(ps\_item) range\_search {real\ x_0,\ real\ x_1,\ real\ y_0,\ real\ y_1}  {}
\+\nop                {returns all items $<p,i>\ \in\ S$ with}
\+\nop                {$x_0 \le p$.xcoord() $\le x_1$ and}
\+\nop                {$y_0 \le p$.ycoord() $\le y_1$}
\smallskip
\+\op list(ps\_item) convex\_hull {}
                      {returns the list of items containing all}
\+\nop                {points of the convex hull of \var\ in clock-}
\+\nop                {wise order.}
\smallskip
\+\op void           del {point\ p}         
                      {deletes the item with point $p$ from \var}
\smallskip
\+\op void           del\_item {ps\_item it}   
                              {removes item $it$ from \var.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op void           change\_inf {ps\_item\ it,\ I\ i} 
                              {makes $i$ the information of item $it$.}
\+\nop                        {\precond $it$ is an item in \var.}
\smallskip
\+\op list(ps\_item) all\_items {}
                              {returns the list of all items in $S$. }
\smallskip
\+\op list(point)    all\_points {}
                              {returns the list of all points in $S$. }
\smallskip
\+\op void           clear {} 
                              {makes \var\ the empty point\_set.}
\smallskip 
\+\op bool           empty {} 
                              {returns true iff \var\ is empty.}
\smallskip 
\+\op int            size {}  
                              {returns the size of \var.}



\bigskip
{\bf 4. Iteration}

{\bf forall\_ps\_items}($i,S$) 
$\{$ ``the items of $S$ are successively assigned to $i$ '' $\}$



\bigskip
{\bf 5. Implementation}

Point sets are implemented by a combination of two-dimensional range trees
and Voronoi diagrams.  Operations insert, lookup, del\_item, del 
take time $O(\log^2 n)$, key, inf, empty, size, change\_inf take time $O(1)$, 
and clear takes time $O(n\log n)$. A range\_search operation takes time
$O(k+\log^2 n)$, where $k$ is the size of the returned list. A nearest\_neighbor
query takes time $O(n^2)$, if it follows any update operation (insert or
delete) and $O(log n)$ otherwise. Here $n$ is the current size of the 
point set. The space requirement is $O(n^2)$.

